#coding=utf-8
#Dijkstra
N, M = map(int, input("请输入结点数，边数： ").split())
cost = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(M):
    s, e, v = map(int, input(f'请输入第{i+1}条边： ').split())
    cost[s - 1][e - 1] = v
flag = [False for i in range(N)]
d = [float('inf') for i in range(N)]
d[0] = 0
while True:
    u = -1
    for i in range(N):
        if (flag[i] == False) and (u == -1 or d[u] > d[i]):
            u = i
    if u == -1:
        break
    flag[u] = True
    for i in range(N):
        d[i] = min(d[i], d[u] + cost[u][i])

for i in range(N):
    print(-1, end=" ") if d[i] == float('inf') else print(d[i], end=" ")

print(f'S到D的最短距离为{d[2]}')
#请输入结点数，边数： 6 9
# 请输入第0条边： 1 2 16
# 请输入第1条边： 2 3 2
# 请输入第2条边： 1 4 4
# 请输入第3条边： 1 5 8
# 请输入第4条边： 5 2 7
# 请输入第5条边： 6 2 5
# 请输入第6条边： 6 3 6
# 请输入第7条边： 4 5 3
# 请输入第8条边： 5 6 1


